package midsearch;

import java.util.Arrays;

/**
 * 题目 ：狒狒吃香蕉
 * 题目详述 ：
 * 狒狒喜欢吃香蕉。这里有 n 堆香蕉，第 i 堆中有piles[i]根香蕉。警卫已经离开了，将在 h 小时后回来。
 *
 * 狒狒可以决定她吃香蕉的速度 k （单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉 k 根。如果这堆香蕉少于 k 根，
 * 她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉，下一个小时才会开始吃另一堆的香蕉。
 * 狒狒喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。
 *
 * ===》
 * 所要求的最终值 ：
 * 返回它可以在 h 小时内吃掉所有香蕉的最小速度 k（k 为整数）。
 */
public class MinEatingSpeed {
    /**
     * 核心思想 ：
     * 主要解决的核心问题在于，如何求取狒狒吃香蕉的最慢速度；
     * (1)所能够确认的是，狒狒吃香蕉的速度范围[1,maxSpeed];
     * (2)若是发现speed速度下，能够符合条件的话，同时还要去判断是否是符合条件的最小速度；（在speed范围的前半部分中进行寻找符合条件的最小速度）
     * 同时，若是不符合条件的话，需要在speed范围的后半部分进行寻找符合条件的最小速度；
     * @param piles
     * @param h
     * @return
     */
    public int minEatingSpeed(int[] piles, int h) {
        // 对于piles数组进行排序（从小到大）
        Arrays.sort(piles);
        // 由于上述对于piles数组从小到大进行了排序，所以piles数组的最后一个元素就是 maxSpeed
        int maxSpeed = piles[piles.length - 1];
        int minSpeed = 1;
        while(minSpeed <= maxSpeed){
            int speed = (minSpeed + maxSpeed) / 2;
            // 即，代表了当前速度下，狒狒能够在警卫员回来之前吃完香蕉；
            if(useTime(piles,speed) <= h){
                // 即，还需要去判断当前速度 是否为最慢速度（即，狒狒能够在警卫员回来之前吃完香蕉的最慢速度）
                if(speed == 1 || useTime(piles,speed - 1) > h){
                    /**
                     * 需要注意的是，由于此处在判断是否为最小符合条件的速度时，会将speed - 1后所需要花费的时间和警卫出去时间进行比较；
                     * 若是当前速度为速度范围内的最小速度，那么当前速度就是符合的最小速度；
                     */
                    // 即，若是当前speed减1的话，则狒狒就来不及在警卫员回来之前吃完香蕉；
                    // ===> 当前速度speed，为最慢速度
                    return speed;
                }
                // 若是当前speed不是符合条件的最慢速度的话，需要在速度范围的前半部分进行寻找符合条件的最慢速度
                maxSpeed = speed - 1;
            }
            else {
                minSpeed = speed + 1;
            }
        }
        // 即，最大速度也不能够实现 狒狒能够在警卫员回来之前吃完所有香蕉；
        return -1;
    }
    // 获取当前速度下，吃完所有香蕉所要花费的时间；
    public int useTime(int[] piles , int speed){
        int time = 0;
        // 遍历所有香蕉堆数组，统计吃完所有香蕉花费的时间
        for (int pile : piles) {
            if(pile % speed != 0){
                time ++;
            }
            time += pile/speed;
        }
        return time;
    }
    /**
     * 分析 ：
     * 时间复杂度 ：O（logn * m） (m，为pile数组中元素元素；n，为pile数组中元素最大值)
     */
}
